【第1676期】Protocol Buffers 编码原理

前言

Protocol Buffers，记得上一次分享是因为有一款游戏服务端跟前端传输数据就是采用这个，这篇大家就权当了解吧。今日早读文章由哔哩哔哩资深后端开发工程师@吕海涛授权分享。

正文从这开始～～

当今云时代 gRPC 大行其道，gRPC 默认的序列化编码 Protocol Buffers 也跟着流行开来。都说 Protocol Buffers 效率很高，那到底高在哪里呢？今天就跟大家讨论一下 Protocol Buffers 的编码规则。

代码里的对象基本分两类，一类的长度是固定的，比如 int32 占用 32 字节，double 占用 64 字节；另一类的长度是变化的，比如字符串。所以，在设计编码的时候，首先就得区分这两种情况。最简单的办法就是用一个字节表示类型，紧接着传输数据，如下图所示：

type data
+--------+--------+~~+--------+
|xxxxxxxx|xxxxxxxx| |xxxxxxxx|
+--------+--------+~~+--------+
7 0 7 0 7 0

一个字节有 256 种取值。我们可以为每一种类型分配一个编号。解码的时候先读出第一个字节，根据不同的类型再读取对应长度的数据。对于定长类型的数据，解码到此就完成了。对于变长类型数据，我们还需要确认数据的长度。如何传输这个长度呢？以 string 为例。先传一个字节表示长度，再传真正的字符串，如下图所示：

type=string length data
+--------+--------+~~+--------+
|xxxxxxxx|xxxxxxxx| |xxxxxxxx|
+--------+--------+~~+--------+
7 0 7 0 7 0

一个字节能表示的最大值是 255，所以字符串的长度不能超过 255 字节。这肯定是不行的。怎么办？如果我们使用两个字节，则最大能表示的长度就会扩展到 65535 字节。这对于一般的使用场景也就够用了。但如果要传输更长的字符串呢？再加字节吗？

因为长度是变化的，所以使用固定长度字节表示很不灵活：太短则表示范围太小；太长则传输效率太低。如果我们用 4 个字节表示长度 1，则为 0x00 0x00 0x00 0x01，高 31 位都是零，没有传递任何信息。

如果能去掉这些零效率不就提上来吗？比如，对于长度 1 只传 0x01，对于长度 4112 只传 0x1010。但就，这样做会导致另外一个问题：如何确定表示长度所需要的字节数量。我们好像以回到了原点。为了表示字符串的长度，我们引入了长度字段，现在长度字段的长度也是不确定的了。

对于这个问题，不同的协议采用了不同的方法。

比如 websockt 协议划定了一个 7bit 的字段表示长度，最大能表示的长度是 127，肯定不够用。所以 websocket 协议还规定，当长度取值为 126 时，紧接着会再传输两个字节表示真正的长度；当取值为 127 时，则紧接着会传再传输八个字节表示真正的长度。这是 RFC6455 的定义消息格式片段：

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-------+-+-------------+-------------------------------+
|F|R|R|R| opcode|M| Payload len | Extended payload length |
|I|S|S|S| (4) |A| (7) | (16/64) |
|N|V|V|V| |S| | (if payload len==126/127) |
| |1|2|3| |K| | |
+-+-+-+-+-------+-+-------------+ - - - - - - - - - - - - - - - +
| Extended payload length continued, if payload len == 127 |
+ - - - - - - - - - - - - - - - +-------------------------------+
~

在 websocket 中，长度为 0~126 占用一个字节；128~65534 占用两个字节、大于 65535 则占用八个字节。websockt 的做法与简单设置固定长度字节相比确实进步了不少。但它只把长度分成三个区间，有点太粗了。比如，长度在 128 到 256 之间话需要占用两个字节；长度一旦超过 65534，则对不住了，八字节走起。

显然，我们需要一个分段粒度更细的方案。这就用到 VarInts 了。

websoket 协议中征用了 126 和 127 这两个数字表示长度字段总共占几个字节，以达到动态扩展的效果。VarInts 则是征用了每个字节的最高位(MSB)。具体表示方式如下表：

0 ~ 2^07 - 1 0xxxxxxx2^07 ~ 2^14 - 1 1xxxxxxx 0xxxxxxx2^14 ~ 2^21 - 1 1xxxxxxx 1xxxxxxx 0xxxxxxx2^21 ~ 2^28 - 1 1xxxxxxx 1xxxxxxx 1xxxxxxx 0xxxxxxx2^28 ~ 2^35 - 1 1xxxxxxx 1xxxxxxx 1xxxxxxx 1xxxxxxx 0xxxxxxx

看到这个表格大家有没有似曾相识的感觉呢？对了，这个表格跟 UTF-8 的编码表很像，具体可以参考我的文章:https://zhuanlan.zhihu.com/p/70264909

简单来说，VarInts 在解码的时候，如果读到的字节的 MSB 是 1 话，则表示还有后序字节，一直读到 MSB 为 0 的字节为止。举个例子，长序 624485 可以作如下编码：

MSB ------------------ LSB
10011000011101100101 <1> 二进制 20bit
0100110 0001110 1100101 <2> 从 LSB 到 MSB 每七位分一组，不足七位高位补零00100110 10001110 11100101 <3> 最右边一组高位补零，其他组高位补一
0x26 0x8E 0xE5 <4> 转换成十六进制→ 0xE5 0x8E 0x26 <5> 从 LSB 到 MSB 输出结果

如果要支持 64 位整数范围，则 VarInts 最多需要 10 个字节。从最大字节占用数来看，VarInts 比 websocket 要差一点。但对于小数字，VarInts 则比 websocket 更加紧凑。大家可以把 websocket 的方法看成是三档变速，把 VarInts 的看成是无级变速。

有了 VarInts，我们就把定长数据和变长数据的表示问题给解决了。那是不是编码设计到此就完成了呢？不然。我们还要解决字段映射的问题。

对于字段映射问题，json 和 xml 都是在编码的时候直接加上字段名，比如：

{
"foo":1,
"bar": "hello"}

这样做最大的好处就是易读，编码和解码逻辑互不依赖。但缺点也很明显，传输效率低。每次都得重复传输字段名，有点浪费。Protocol Buffers 采用了另一种策略，给字段加编号。举个例子：

message Foo {
int32 foo = 1;
string bar = 2;}

请大家留意每个字段等号后面的数字。这个数字也叫 tag，不能重复，跟字段一一对应。Protocol Buffers 每个字段编码后从逻辑上分为三个部分：

<tag> <type> [<length>] <data>

tag, type, 和 length 都用 VarInts 表示。

Protocol Buffers 在 3 版本中定义了 4 种类型 type：

• 0 VarInt 表示 int32, int64, uint32, uint64, sint32, sint64, bool, enum

• 1 64-bit 表示 fixed64, sfixed64, double

• 2 Length-delimited 表示 string, bytes, embedded messages, repeated 字段

• 5 32-bit 表示 fixed32, sfixed32, float

其中 3 和 4 表示的类型已经废弃，不多讨论。因为类型比较少，所以 Protocol Buffers 在编码的时候只用了 3 比特，实际传输的时候是以 (tag<<3)|type 的方式传输的。

举个例子。如果前面的 Foo 的 foo 字段取值为 1 的话，则对应的编码是：0x08 0x01。foo 的类型是 int32，对应的 type 取 0。而它的 tag 又是 1，所以第一个字节是 (1<<3)|0 = 0x08，第二个字节是数字 1 的 VarInts 编码，即 0x01。

7 0 7 0+-----+---+--------+|00001|000|00000001|+-----+---+--------+
tag type data

再举个字符串的例子。如果 Foo 的 bar 字段取值为 吕 的话，则对应的编码是：0x12 0x03 0xe5 0x90 0x95。bar 的类型是 string，对应的 type 取 2。而它的 tag 又是 2，所以第一个字节是 (2<<3)|2 = 0x12，第二个字节表示字符串的长度为 3，再后面 3 个字节是汉字吕 UTF-8 编码。

7 0 7 0 25 0+-----+---+--------+===========+|00010|010|00000011|0xe50x90x95|+-----+---+--------+===========+
tag type length utf-8

使用 tag 的优点是不用重复传输字段名，但也是它的缺点。因为没有字段名，所以编码和解码的代码必须持有一份字段名和 tag 的映射关系，这是在生成代码的时候自动完成的。也就是说，没有 proto 文件，你是没法对 Protocol Buffers 数据进行解码的。

Protocol Buffers 还支持自定义消息字段和 repeated 字段。这两种自段在编码上跟 string 是等价的。先举个 repeated 字段的例子。

message Baz {
int32 b = 1;}
message Bar {
repeated int32 a = 1;
Baz b = 2;}

如果我们让 Bar 和 a 字段取 [1,2,3]，让 b 字段取 {b:4}，则对应的编码为 0x0a 0x03 0x01 0x02 0x03 0x12 0x02 0x08 0x04。这段数据可以拆成两部分：

• 0x0a 0x03 0x01 0x02 0x03

• 0x12 0x02 0x08 0x04

先说第一部分。因为 a 的类型为 repeated int32，所以对应 type 取 2；又 a 和 tag 为 1，所以第一个字节应该是 (1<<3|2) = 0x0a。第二个字节表示数组长度，所以是 0x03，接下来三个字节分别是 1, 2, 3 的 VarInts 编码。

再说第二部分。因为 b 的类型为 Bar，所以对应的 type 也是 2；又 b 的 tag 为 2，所以第一个字节应该是(2<<3|2) = 0x12。第二个字节表示 message 的长度，所以是 0x02，接下来两个字节表示 Baz 的编码。

7 0 7 0 25 0 7 0 7 0 7 0 7 0+-----+---+--------+===========+-----+---+--------+=====+===+========+|00001|010|00000011|0x010x02x03|00010|010|00000010|00001|000|00000100|+-----+---+--------+===========+-----+---+--------+=====+===+========+
tag type length utf-8 tag type length tag type data
|<----- baz.b ---->||<---------- foo.a ----------->|<-------------- foo.b -------------->|

单从数据来看，我们无法区分 string，repeated 和 message。要想解析这类数据，必须依赖 proto 定义。

VarInts 不太适合表示负数。因为负数在计算机使用补码表示，转成 unit64 是一个很大的数。当你使用 VarInts 表示的时候，-1 居然要占用 10 个字节(0xff 0xff 0xff 0xff 0xff 0xff 0xff 0xff 0xff 0x01)！是可忍，孰不可忍！为此，Protocol Buffers 引入了 sint32 和 sint64 两种类型，在编码的时候先将数字转化成 ZigZag 编码。ZigZag 思想也很简单，就是用正数来表示负数，映射规则如下：

+-- 0 -1 1 -2 2 -3 3...
| +--+--+--+--+--+--+---->
+-> 0 1 2 3 4 5 6...

同样的，单从数据来看，我们也是没法区分整数是不是用了 ZigZag 编码处理，这些信息只能从 proto 文件获取。

Protocol Buffers 还有一个问题需要注意，那就是 tag 的取值范围。因为使用了 VarInts，所以单字节的最高位是零，而最低三位表示类型，所以只剩下 4 位可用了。也就是说，当你的字段数量超过 16 时，就需要用两个以上的字段表示了。

好了，写到这里，Protocol Buffers 的编码也就说得差不多了。总结几条使用 Protocol Buffers 需要注意的事项：

• 不要修改字段 tag

• 字段尽量不要超过 16 个

• 尽量使用小整数

• 如果需要传输负数，请使用 sint32 或 sin64

参考文献：

https://developers.google.com/protocol-buffers/docs/encoding
https://www.deadalnix.me/2017/01/08/variable-size-integer-encoding/
https://carlmastrangelo.com/blog/lets-make-a-varint
https://en.wikipedia.org/wiki/LEB128
https://tools.ietf.org/html/rfc6455#section-5.2

关于本文
作者：@吕海涛
原文：https://zhuanlan.zhihu.com/p/73549334

为你推荐